package heap;

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * @author 26233
 * 大根堆数组实现
 */
public class BigRootHeap {
	
	// 数组扩容交给List系统处理
	List<Integer> bigHeapArray = new ArrayList<Integer>();
	
	int count = 0;
	
	// 根据有限数据构造
	public void init(int[] data) {
		for(int i = 0; i < data.length; i++) {
			bigHeapArray.add(data[i]);
			heapfyUp(bigHeapArray);
			count++;
		}
		
	}
	
	// 根据不确定数量数据构造
	public void add(int data) {
		bigHeapArray.add(data);
		heapfyUp(bigHeapArray);
		count++;
	}
	
	public int pop() {
		
		int result = bigHeapArray.get(0);
		int lastIndex = bigHeapArray.size() - 1;
		bigHeapArray.set(0, bigHeapArray.get(lastIndex));
		bigHeapArray.remove(lastIndex);
		
		heapfyDown(bigHeapArray);
		
		count--;
		
		return result;
	}
	
	public void delete(int data) {}
	
	// 删除头元素时，末尾元素交换到头元素位置，然后向下调整
	public void heapfyDown(List<Integer> bigHeapArray) {
		int index = 0;
		while(index < bigHeapArray.size()) {
			int leftChildIndex = index * 2 + 1;
			int rightChildIndex = index * 2 + 2;
			
			if(leftChildIndex >= bigHeapArray.size() && rightChildIndex >= bigHeapArray.size()) {
				break;
			}else {
				if(leftChildIndex >= bigHeapArray.size()) {
					if(bigHeapArray.get(rightChildIndex) > bigHeapArray.get(index)) {
						int temp = bigHeapArray.get(rightChildIndex);
						bigHeapArray.set(rightChildIndex, bigHeapArray.get(index));
						bigHeapArray.set(index, temp);
						
						index = rightChildIndex;
					}else {
						break;
					}
				}else if(rightChildIndex >= bigHeapArray.size()) {
					if(bigHeapArray.get(leftChildIndex) > bigHeapArray.get(index)) {
						int temp = bigHeapArray.get(leftChildIndex);
						bigHeapArray.set(leftChildIndex, bigHeapArray.get(index));
						bigHeapArray.set(index, temp);
						
						index = leftChildIndex;
					}else {
						break;
					}
				}else {
					int maxIndex = index;
					if(bigHeapArray.get(leftChildIndex) > bigHeapArray.get(maxIndex)) {
						maxIndex = leftChildIndex;
					}
					if(bigHeapArray.get(rightChildIndex) > bigHeapArray.get(maxIndex)) {
						maxIndex = rightChildIndex;
					}
					
					if(maxIndex == index) {
						break;
					}else {
						
						int temp = bigHeapArray.get(maxIndex);
						bigHeapArray.set(maxIndex, bigHeapArray.get(index));
						bigHeapArray.set(index, temp);
						
						index = maxIndex;
					}
				}
			}
			
		}
	}
	
	public int peek() {
		return bigHeapArray.get(0);
	}
	
	public List<Integer> getBigHeapArray() {
		return bigHeapArray;
	}

	public void setBigHeapArray(List<Integer> bigHeapArray) {
		this.bigHeapArray = bigHeapArray;
	}

	public int getCount() {
		return count;
	}

	public void setCount(int count) {
		this.count = count;
	}

	// 添加元素后向上调整
	public void heapfyUp(List<Integer> bigHeapArray) {
		int index = bigHeapArray.size() - 1;
		while(index > 0) {
			if(bigHeapArray.get((index -1) / 2) < bigHeapArray.get(index)) {
				// 交换
				int temp = bigHeapArray.get(index);
				bigHeapArray.set(index, bigHeapArray.get((index -1) / 2));
				bigHeapArray.set((index -1) / 2, temp);
			}
			index = (index -1) / 2;
		}
	}
	
	public static void main(String[] args) {
		
		int[] arr = new int[] {5, 4, 6, 1, 7, 2, 3, 9, 8};
		BigRootHeap bigRootHeap = new BigRootHeap();
		bigRootHeap.init(arr);
		
		bigRootHeap.add(10);
		
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
//		System.out.println(bigRootHeap.pop());
		
		System.out.println("end");
	}

}
